package com.zac.coroutine.algorithm.leetcode.others

/**
 * author zac
 * date 2024/11/5
 * --简单--
 *
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 *
 * 做不出来
 */
class Test6 {

    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            val startTime = System.currentTimeMillis()
            print("Fibonacci number at position " + 1000 + " is: " + fibonacci(1000));
            val endTime = System.currentTimeMillis()
            print(" 时间:${endTime - startTime}")
        }

        private fun climbStairs(n: Int) {

        }

        /**
         * 递归
         * 求第n个斐波那契数
         */
        private fun fibonacci(n: Int): Int {
            return if (n <= 0) {
                0
            } else if (n == 1) {
                1
            } else {
                fibonacci(n - 1) + fibonacci(n - 2);
            }
        }

        /**
         * 动态规划
         * 求第n个斐波那契数
         */
        private fun fibonacciDP(n: Int): Int {
            if (n <= 0) {
                return 0
            } else if (n == 1) {
                return 1
            }
            val dp = IntArray(n + 1)
            dp[0] = 0
            dp[1] = 1
            for (i in 2 until n + 1) {
                dp[i] = dp[i - 1] + dp[i - 2]
            }
            return dp[n]


        }


    }


}